#include <cstdlib>
#include <iostream>
#include <cstdbool>
#include "BinaryTree.h"

BSTree::BSTree()
{
    this->root = new BTNode(NULL);
}

BSTree::BSTree(void (*ClearPtr)(ElementType))
{
    this->root = NULL;
    this->ClearPtr = ClearPtr;
}

ElementType BSTree::GetNodeData(BTNode *n)
{
    if (n == NULL) 
    {
        std::cerr << "节点不存在\n";
        return NULL;
    } 
    else 
    {
        return n->data;
    };
}

BTNode *BSTree::GetTreeRoot()
{
    return this->root;
}


void BTNode::InsertNodeTree(ElementType element, int (*funcPtr)(ElementType, ElementType))
{
    if(this == NULL)
        return;
    
    //元素比节点小且左孩子为空
    if(funcPtr(this->data,element) > 0 && this->left == NULL)
    {
        this->left = new BTNode(element);
        if(this->left == NULL)
            return;
        //将创建节点的双亲指向自己
        this->left->parent = this;
        return;
    }

    //元素比节点大且右孩子为空
    if(funcPtr(this->data,element) < 0 && this->right == NULL)
    {
        this->right = new BTNode(element);
        if(this->right == NULL)
            return;
        //将创建节点的双亲指向自己
        this->right->parent = this;
        return;
    }

    //如果数相同直接不做操作
    if(funcPtr(this->data,element) == 0)
        return;

    if(funcPtr(this->data,element) > 0)
        //递归,和左孩子比较
        InsertNodeTree(element,funcPtr);
    else
        //递归,和右孩子比较
        InsertNodeTree(element,funcPtr);
}



void BSTree::InsertElement(ElementType element, int (*funcPtr)(ElementType, ElementType))
{
    if (root == NULL) 
    {
        root = new BTNode(element);
    } 
    else 
    {
        root->InsertNodeTree(element,funcPtr);
    }
}

void BSTree::TravelPrev(BTNode *node, void (*funcPtr)(ElementType))
{
    if (node == NULL) return;
    funcPtr(node->data);
    TravelPrev(node->left, funcPtr);
    TravelPrev(node->right, funcPtr);
}

void BSTree::TravelMid(BTNode *node, void (*funcPtr)(ElementType))
{
    if (node == NULL) return;
    TravelMid(node->left, funcPtr);
    funcPtr(node->data);
    TravelMid(node->right, funcPtr);
}

void BSTree::TravelPost(BTNode *node, void (*funcPtr)(ElementType))
{
    if (node == NULL) return;
    TravelPost(node->left, funcPtr);
    TravelPost(node->right, funcPtr);
    funcPtr(node->data);
}



BTNode *BTNode::FindNode(ElementType element, int (*funcPtr)(ElementType, ElementType))
{
    if(this == NULL)
        return NULL;
    //当前节点的值等于要找的值
    if(funcPtr(this->data,element) == 0)
        return this;
    //当前节点的值大于要找的值,往左找
    else if(funcPtr(this->data,element) > 0)
    {
        return FindNode(element,funcPtr);
    }
    //当前节点的值小于要找的值,往右找
    else
    {
        return FindNode(element,funcPtr);
    }
}

BTNode *BSTree::FindByElement(ElementType element, int (*funcPtr)(ElementType, ElementType))
{
    return root->FindNode(element,funcPtr);
}





//判断一个节点是不是另一个节点的左孩子
bool BTNode::IsLeftChild()
{
    if(this->left == this)
        return true;
    return false;
}





//删除一个节点
void BSTree::RemoveByElement(ElementType element, int (*funcPtr)(ElementType, ElementType))
{
    BTNode *node = FindByElement(element,funcPtr);
    if(node == NULL)
        return;
    //要删除一个节点,需要先找到这个节点
    //该节点是叶子节点(左右孩子都空)
    if(node->left == NULL && node->right == NULL)
    {
        //如果该节点是根节点(整棵树就它一个节点)
        if(node->parent == NULL)
        {
            free(node);
            root = NULL;
            return;
        }

        //该节点是双亲的左孩子
        if(node->IsLeftChild() == true)
            node->parent->left = NULL;
        //该节点是双亲的右孩子
        else
            node->parent->right = NULL;
        
        free(node);
    }

    //左孩子不空,右孩子空
    else if(node->right == NULL)
    {
        node->left->parent = node->parent;
        //该节点是根节点
        if(node->parent == NULL)
        {
            root = node->left;
            free(node);
            return;
        }

        //该节点是双亲的左孩子
        if(node->IsLeftChild() == true)
            node->parent->left = node->left;
        //该节点是双亲的右孩子
        else
            node->parent->right = node->left;

        free(node);
    }
    //左孩子空,右孩子不空
    else if(node->left == NULL)
    {
        node->right->parent = node->parent;
        //该节点是根节点
        if(node->parent == NULL)
        {
            root = node->right;
            free(node);
            return;
        }
        //该节点是双亲的左孩子
        if(node->IsLeftChild() == true)
            node->parent->left = node->right;
        //该节点是双亲的右孩子
        else
            node->parent->right = node->right;

        free(node);
    }
    //左右孩子都不空
    else
    {
        //找右边子树最小的节点
        BTNode *MinNode = node->right;
        while(MinNode->left != NULL)
        {
            MinNode = MinNode->left;
        }

        //交换两个节点的值
        node->data = MinNode->data;

        //最左边的节点也可能有右子节点

        //如果右边子树的最小节点碰巧就是右孩子
        if(MinNode->parent == node)
            node->right = MinNode->right;
        else
            MinNode->parent->left = MinNode->right;
        free(MinNode);
    }
}


BTNode *BTNode::RotateLeft()
{
    BTNode *t = this->right;
    t->parent = this->parent;
    this->right = t->left;
    t->left = this;
    this->parent = t;
    if(this->right != NULL)
        this->right->parent = this;
    return t;
}

BTNode *BTNode::RotateRight()
{
    BTNode *t = this->left;
    
    t->parent = this->parent;
    this->left = t->right;
    t->right = this;
    this->parent = t;
    if(this->left != NULL)
        t->left->parent = this;
    return t;
}

BTNode *BTNode::RotateLeftRight()
{
    this->left = RotateLeft();
    return RotateRight();
}

BTNode *BTNode::RotateRightLeft()
{
    this->right = RotateRight();
    return RotateLeft();
}

int BTNode::GetNodeHeight(BTNode *node)
{
    if(this == NULL)
        return 0;
    
    int leftHeight = GetNodeHeight(node->left);
    int rightHeight = GetNodeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

int BSTree::GetTreeHeight(BSTree *tree)
{
    if(root == NULL)
        return 0;
    
    int leftHeight = root->GetNodeHeight(root->left);
    int rightHeight = root->GetNodeHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

BTNode *BTNode::InsertNode(BTNode *node, ElementType element, int (*funcPtr)(ElementType, ElementType))
{
    if(node == NULL)
    {
        //node = CreateBTNode(element);
        return node;
    }
        
    if(funcPtr(node->data,element) > 0 && node->left == NULL)
    {
        node->left = new BTNode(element);
        if(node->left == NULL)
            return node;
        node->left->parent = node;
        
        return node;
    }
    if(funcPtr(node->data,element) < 0 && node->right == NULL)
    {
        node->right = new BTNode(element);
        if(node->right == NULL)
            return node;
        node->right->parent = node;
       
        return node;
    }
    // if(node->data == element)
    //     return node;
    if(funcPtr(node->data,element) > 0)
    {
        node->left = InsertNode(node->left,element,funcPtr);
        if(GetNodeHeight(node->left) - GetNodeHeight(node->right) > 1)
        {
            //左左插入
            if(funcPtr(node->left->data,element) > 0)
                node = node->RotateRight();
            //左右插入
            else
                node = node->RotateLeftRight();  
        }
    }
        
    if(funcPtr(node->data,element) < 0)
    {
        node->right = InsertNode(node->right,element,funcPtr);
        if(GetNodeHeight(node->right) - GetNodeHeight(node->left) > 1)
        {
            //右右插入
            if(funcPtr(node->right->data,element) < 0)
                node = node->RotateLeft();
            //右左插入
            else
                node = node->RotateRightLeft();
        }
    }
    return node;    
}



void *BSTree::InsertTree(ElementType element, int (*funcPtr)(ElementType, ElementType))
{
    if(root == NULL)
    {
        //node = CreateBTNode(element);
        return root;
    }
        
    if(funcPtr(root->data,element) > 0 && root->left == NULL)
    {
        root->left = new BTNode(element);
        if(root->left == NULL)
            return root;
        root->parent = root;
        
        return root;
    }
    if(funcPtr(root->data,element) < 0 && root->right == NULL)
    {
        root->right = new BTNode(element);
        if(root->right == NULL)
            return root;
        root->right->parent = root;
       
        return root;
    }
    // if(node->data == element)
    //     return node;
    if(funcPtr(root->data,element) > 0)
    {
        root->left = root->left->InsertNode(root->left,element,funcPtr);
        if(root->GetNodeHeight(root->left) - root->GetNodeHeight(root->right) > 1)
        {
            //左左插入
            if(funcPtr(root->left->data,element) > 0)
                root = root->RotateRight();
            //左右插入
            else
                root = root->RotateLeftRight();  
        }
    }
        
    if(funcPtr(root->data,element) < 0)
    {
        root->right = root->right->InsertNode(root->right,element,funcPtr);
        if(root->GetNodeHeight(root->right) - root->GetNodeHeight(root->left) > 1)
        {
            //右右插入
            if(funcPtr(root->right->data,element) < 0)
                root = root->RotateLeft();
            //右左插入
            else
                root = root->RotateRightLeft();
        }
    }
    return root;    
}

BTNode *BTNode::RemoveNodeElement(BTNode *node,ElementType element)
{
    // BTNode *node = FindNodeElement(root,element);
    // if(node == NULL)
    //     return root;
    BTNode *temp = node->parent;
    if(node->left == NULL && node->right == NULL)
    {
        if(node->parent == NULL)
        { 
            node = NULL;
            free(node);
            return temp;
        }
        if(node->IsLeftChild() == true)
            node->parent->left = NULL;
        else
            node->parent->right = NULL;
        free(node);
        return NULL;
    }
    else if(node->left == NULL)
    {
        node->right->parent = node->parent;
        if(node->parent == NULL)
        {
            node = node->right;
            free(node->right);
            return node;
        }
        if(node->IsLeftChild() == true)
            node->parent->left = node->right;
        else
            node->parent->right = node->right;
        free(node);
        return temp->right;
    }
    else if(node->right == NULL)
    {
        node->left->parent = node->parent;
        if(node == NULL)
        {
            node = node->left;
            free(node->left);
            return node;
        }
        if(node->IsLeftChild() == true)
            node->parent->left = node->left;
        else
            node->parent->right = node->left;
        free(node);
        return temp->left;
    }
    else
    {
        BTNode *MinNode = node->right;
        while(MinNode->left != NULL)
        {
            MinNode = MinNode->left;
        }
        node->data = MinNode->data;
        if(node->right == MinNode)
            node->right = MinNode->right;
        else
            MinNode->parent->left = MinNode->left;
        free(MinNode);
        return node;
    }
}



BTNode *BTNode::DeleteNode(BTNode *node, ElementType element, int (*funcPtr)(ElementType, ElementType))
{
    if(node == NULL)
        return NULL;

    if(funcPtr(node->data,element) > 0)
    {
        node->left = DeleteNode(node->left,element,funcPtr);
        //右子树重
        if(GetNodeHeight(node->right) - GetNodeHeight(node->left) > 1)
        {
            //右孩子的左子树比右子树高
            //右左
            if(GetNodeHeight(node->right->left) - GetNodeHeight(node->right->right) > 0)
                node = node->RotateRightLeft();
            else
                node = node->RotateLeft();
        }
    }
    else if(funcPtr(node->data,element) < 0)
    {
        node->right = DeleteNode(node->right,element,funcPtr);
        //左边重
        if(GetNodeHeight(node->left) - GetNodeHeight(node->right) > 1)
        {
            //左左
            if(GetNodeHeight(node->left->left) - GetNodeHeight(node->left->right) > 0)
                node = node->RotateRight();
            //左右
            else
                node = node->RotateLeftRight();
        }
    }
    //找到要删除的节点
    else
    {
        node = RemoveNodeElement(node,element);
    }
    return node;
}

void *BSTree::DeleteTree(ElementType element, int (*funcPtr)(ElementType, ElementType))
{
    root = root->DeleteNode(root,element,funcPtr);
    return root;
}
